﻿//
// Copyright 2008-2011 by Burt Harris
// Licensed under the Microsoft Public License (Ms-PL)
// See: http://www.codeplex.com/yaml/license
//

using System;
using System.Diagnostics.Contracts;
using System.Runtime.InteropServices;

namespace YaTools.Yaml
{
    /// <summary>
    /// Tool to avoid generating a lot of garbage while parsing.   It caches
    /// commonly used substrings (e.g. "1" or "true") so that they don't need to be
    /// allocated each time parsed out of a buffer.   
    /// 
    /// Consider an implementation based on Hopscotch Hashing.
    /// http://www.cs.tau.ac.il/~liortzaf/papers/disc2008_submission_98.pdf
    /// </summary>
    internal sealed class StringCache
    {
        private const int InitialSize = 512; // Important: Must be a power of two

        private readonly HashSet<Bucket> _bucketSet = new HashSet<Bucket>();
        private readonly HashSet<WeakBucket> _weakBucketSet = new HashSet<WeakBucket>();

        // ReSharper disable UnusedMember.Local
        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant(_bucketSet != null);
            Contract.Invariant(_weakBucketSet != null);
        }

        // ReSharper restore UnusedMember.Local

        internal string GetString(BufferSegment segment)
        {
            string value;

            if (segment.SegmentLength == 0) return String.Empty;

            int bucketIndex = _bucketSet.FindBucket(segment); // Search main cache
            if (bucketIndex >= 0) // Found it
            {
                value = _bucketSet[bucketIndex].ToString();
                // Trace.WriteLine(Utility.DebugDisplay(value), "Reused");
                return value;
            }

            int weakIndex = _weakBucketSet.FindBucket(segment); // Search weak cache
            if (weakIndex >= 0)
            {
                value = _weakBucketSet[weakIndex].ToString();
                if (value != null)
                {
                    _bucketSet.Add(bucketIndex, new Bucket(value, segment), segment);
                    _weakBucketSet.RemoveAt(weakIndex);
                    //Trace.WriteLine(Utility.DebugDisplay(value), "Cached");
                    return value;
                }
                // Corner case, thought we found it in the weak set, but couldn't retrieve the string
                // Handling this by dropping through as if weak set failed.
                weakIndex = ~weakIndex;
            }

            value = segment.ToString();
            _weakBucketSet.Add(weakIndex, new WeakBucket(value, segment), segment);
            return value;
        }

        private interface IBucket : IEquatable<BufferSegment>
        {
            bool Collided { get; set; }
            bool IsAllocated { get; }
        }

        private struct Bucket : IBucket, IEquatable<Bucket>
        {
            private int _hash;
            private readonly string _value;
            private const int Mask = 0x7FFFFFFF;
            private const int Highbit = unchecked((int) 0x80000000);

            //public Bucket(BufferSegment segment)
            //{
            //    _hash = segment.GetHashCode() & mask;
            //    _value = segment.ToString();
            //}

            public Bucket(string value, BufferSegment segment)
            {
                Contract.Requires(value != null);
                _hash = segment.GetHashCode() & Mask;
                _value = value;
            }

            // ReSharper disable UnusedMember.Local
            [ContractInvariantMethod]
            private void ObjectInvariant()
            {
                Contract.Invariant(_value != null);
            }

            // ReSharper restore UnusedMember.Local

            public bool IsAllocated
            {
                get { return _value != null; }
            }

            public bool Collided
            {
                get { return (this._hash & Highbit) == Highbit; }
                set { _hash = this._hash & Mask | (value ? Highbit : 0); }
            }

            public override string ToString()
            {
                return _value;
            }

            public int GetHashCode(BufferSegment obj)
            {
                return _hash & Mask;
            }

            public bool Equals(BufferSegment other)
            {
                if ((this._hash & Mask) != (other.GetHashCode() & Mask)) return false;
                if (this._value.Length != other.SegmentLength) return false;

                for (int i = 0; i < this._value.Length; i++)
                {
                    if (this._value[i] != other[i]) return false;
                }
                return true;
            }

            public bool Equals(Bucket other)
            {
                if ((this._hash & Mask) != (other._hash & Mask)) return false;
                return this._value.Equals(other._value, StringComparison.InvariantCulture);
            }
        }

        private struct WeakBucket : IBucket, IEquatable<WeakBucket>
        {
            private const int Mask = 0x7FFFFFFF;
            private const int Highbit = unchecked((int) 0x80000000);
            private int _hash;
            private GCHandle _handle;

            public WeakBucket(string value, BufferSegment segment)
            {
                _handle = GCHandle.Alloc(value, GCHandleType.Weak);
                _hash = segment.GetHashCode() & Mask;
            }

            public override int GetHashCode()
            {
                return _hash & Mask;
            }

            public bool IsAllocated
            {
                get { return _handle.IsAllocated; }
            }

            public bool Collided
            {
                get { return (this._hash & Highbit) == Highbit; }
                set { _hash = this._hash & Mask | (value ? Highbit : 0); }
            }

            public override string ToString()
            {
                Contract.Assume(_handle.IsAllocated);
                return _handle.Target as string ?? "<weak value lost>";
            }

            public bool Equals(BufferSegment other)
            {
                if (!this._handle.IsAllocated) return false;
                if ((this._hash & Mask) != (other.GetHashCode() & Mask)) return false;
                string s = this.ToString();
                if (s == null || s.Length != other.SegmentLength) return false;

                for (int i = 0; i < s.Length; i++)
                {
                    if (s[i] != other[i]) return false;
                }

                return true;
            }

            public bool Equals(WeakBucket other)
            {
                if ((this._hash & Mask) != (other._hash & Mask)) return false;
                string s1 = this.ToString();
                if (s1 == null) return false;
                return s1.Equals(other.ToString(), StringComparison.InvariantCulture);
            }
        }

        private class HashSet<T> where T : IBucket, IEquatable<T>, new()
        {
            private int _count, _mask;
            private T[] _buckets;

            public HashSet()
            {
                AllocateBuckets(InitialSize);
            }

            // ReSharper disable UnusedMember.Local
            [ContractInvariantMethod]
            private void ObjectInvariant()
            {
                Contract.Invariant(_buckets != null);
                Contract.Invariant(_buckets.Length > 0);
                Contract.Invariant(_mask == _buckets.Length - 1);
            }

            // ReSharper restore UnusedMember.Local

            public T this[int index]
            {
                get
                {
                    if (index < 0) throw new ArgumentOutOfRangeException("index");
                    return _buckets[index];
                }
            }

            public void Add(int index, T value, BufferSegment segment)
            {
                _count++;
                if (NeedsRehash())
                {
                    ReHash();
                    index = FindBucket(segment);
                }
                index = FindFreeBucket(index);
                _buckets[index] = value;
            }

            public void RemoveAt(int index)
            {
                bool collided = _buckets[index].Collided;
                _buckets[index] = new T();
                if (collided) _buckets[index].Collided = true;
            }

            private void AllocateBuckets(int size)
            {
                Contract.Requires(size > 0);
                Contract.Ensures(this._buckets != null);

                _mask = size - 1;
                _buckets = new T[size];
            }

            private bool NeedsRehash()
            {
                Contract.Requires(this._buckets != null);
                if (_count*2 + 1 < _buckets.Length) return false;

                // Recount just in case

                int allocated = 0;
                int collided = 0;

                foreach (var bucket in _buckets)
                {
                    if (bucket.IsAllocated) allocated++;
                    if (bucket.Collided) collided++;
                }

                _count = allocated;

                if (_count*2 + 1 < _buckets.Length) return false;
                return true;
            }

            private void ReHash()
            {
                T[] oldBuckets = _buckets;
                AllocateBuckets(oldBuckets.Length*2);
                foreach (var bucket in oldBuckets)
                {
                    if (bucket.IsAllocated)
                    {
                        bucket.Collided = false;
                        int i = FindBucket(bucket);
                        _buckets[FindFreeBucket(i)] = bucket;
                    }
                }
            }

            /// <summary>
            /// Find the bucket index for a bucket
            /// </summary>
            /// <param name="segment">The BufferSegment to search for.</param>
            /// <returns>Integer index.  When value is non-negative, the search succeeded, 
            /// otherwise it's the ones-complement index of the first non-collided bucket</returns>
            public int FindBucket(BufferSegment segment)
            {
                int hash = segment.GetHashCode();

                for (int i = 0; i < _buckets.Length; i++)
                {
                    int j = (i + hash) & _mask;
                    T b = _buckets[j];
                    if (b.Equals(segment)) return j;
                    if (!b.Collided) return ~j;
                }
                throw new InvalidOperationException("Hash table should not be full");
            }

            private int FindBucket(WeakBucket segment)
            {
                Contract.Requires(this._buckets != null);
                int hash = segment.GetHashCode();

                for (int i = 0; i < _buckets.Length; i++)
                {
                    int j = (i + hash) & _mask;
                    T b = _buckets[j];
                    if (b.Equals(segment)) return j;
                    if (!b.Collided) return ~j;
                }
                throw new InvalidOperationException("Hash table should not be full");
            }

            private int FindBucket(Bucket segment)
            {
                int hash = segment.GetHashCode();

                for (int i = 0; i < _buckets.Length; i++)
                {
                    int j = (i + hash) & _mask;
                    T b = _buckets[j];
                    if (b.Equals(segment)) return j;
                    if (!b.Collided) return ~j;
                }
                throw new InvalidOperationException("Hash table should not be full");
            }

            private int FindBucket(T bucket)
            {
                Contract.Requires(this._buckets != null);
                int hash = bucket.GetHashCode();

                for (int i = 0; i < _buckets.Length; i++)
                {
                    int j = (i + hash) & _mask;
                    T b = _buckets[j];
                    if (b.Equals(bucket)) return j;
                    if (!b.Collided) return ~j;
                }
                throw new InvalidOperationException("Hash table should not be full");
            }

            private int FindFreeBucket(int foundIndex)
            {
                Contract.Requires(this._buckets != null);
                foundIndex = ~foundIndex;

                for (int i = 0; i < _buckets.Length; i++)
                {
                    int j = (i + foundIndex) & this._mask;
                    T b = _buckets[j];
                    if (!b.IsAllocated) return j;
                    if (!b.Collided) _buckets[j].Collided = true;
                }

                throw new InvalidOperationException("Hash table should not be full");
            }
        }
    }
}